| From: | cheila |
| Date: | 5 May 99 at 17:38:55 |
| Subject: | Re: [amos-list] Crossing lines, fast. |
From: <cheila@saintolaves.demon.co.uk>
Hi
Here is a nice algorithm to check if line segments cross:
Input:
Line1: x0,y0 - x1,y1
Line2: u0,v0 - u1,v1
(with _1 >= _0)
Step 1: Check bounding boxes
if u0 > x1 then not cross
if u1 < x0 then not cross
if v0 > y1 then not cross
if v1 < y0 then not cross
Step 2: Check cross
line1: x = x1*t + (1-t)*x0, y = y1*t + (1-t)*y0
line2: x = u1*s + (1-s)*u0, y = v1*s + (1-s)*v0
solve for s, t (simultaneous equations, simple)
if 0 <= t <= 1 and 0 <= s <= 1 then cross
Step 3: Find intersection (may not be needed)
substitute t or s to find x, y
I think this is one of the best algorithms, but there may
be some more. There are more complicated versions for
polygons in 3D (if that's what you're doing).
Hope this helps
Claude
------------------------------------------------------------------------
Wanting to get back in touch with old friends?
http://www.onelist.com
Reunite through a ONElist community.
------------------------------------------------------------------------
Official AMOS WWW: http://members.xoom.com/AmosFactory/front.html